`
https://leetcode.cn/problems/redundant-connection/
`

/**
 * @param {number[][]} edges
 * @return {number[]}
 */
var findRedundantConnection = function (edges) {
  const uf = new UF(edges.length)
  // 记录联通量
  let count = uf.count()
  for (const edge of edges) {
    uf.union(edge[0], edge[1])
    // 如果加上新的边后，连通量没有变化，说明这条边是冗余的
    if (uf.count() === count) {
      return edge
    } else {
      count = uf.count()
    }
  }
};

class UF {
  // n 为图中节点的个数
  constructor(n) {
    // 连通分量个数
    this._count = n
    // 存储每个节点的父节点
    this.parent = Array.from({ length: n }, (_, index) => index)
  }

  // 将节点 p 和节点 q 连通
  union(p, q) {
    const rootP = this._find(p)
    const rootQ = this._find(q)

    if (rootP === rootQ) {
      return
    }

    this.parent[rootQ] = rootP
    // 两个连通分量合并成一个连通分量
    this._count--
  }

  // 判断节点 p 和节点 q 是否连通
  connected(p, q) {
    const rootP = this._find(p)
    const rootQ = this._find(q)
    return rootP === rootQ
  }

  // 返回图中的连通分量个数
  count() {
    return this._count
  }

  _find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this._find(this.parent[x])
    }
    return this.parent[x]
  }
}